\section{Related Work}
\label{sec:game.related}

Non-cooperative game theory has been used in analyzing a number of
problems in traffic and communication networks, e.g., routing
\cite{roughgarden}, topology control and network formation
\cite{eidenbenz:monet06, nahir:infocom09} and security
\cite{grossklags, orda:infocom09}. The basic questions of interest
have usually been about the existence and the structure of Nash
equilibria and the price of anarchy, which is the worst case cost of a
Nash equilibrium to the social optimum, as defined formally later. See
\cite{nisan:book} for a good introduction on the use of game theoretic
techniques for networking applications.

Several formulations have been proposed for analyzing network security
problems and the spread of epidemics in
networks~\cite{AspnesCY2006,aspnes07,berger05,ganesh05,grossklags,lelarge+b:security,wang03}.
This thesis directly builds on the formulation of Aspnes et
al. \cite{AspnesCY2006}, who model the risk of infection for an
insecure node $v$ as the probability that the initial infection, which
is assumed to originate at a node chosen uniformly at random, starts
in the same component as $v$ in the subgraph induced by $v$ and the
other insecure nodes.  They show the surprising result that pure Nash
equilibria always exist in such games.  They also establish a high
price of anarchy and give an $O(\log^{1.5}{n})$ approximation
algorithm for computing the social optimum, where $n$ is the number of
nodes in the network.  Their approximation algorithm uses an
$O(\sqrt{\log n})$-approximation for the sparsest cut
problem~\cite{arora+rv:cut}, which is based on a semidefinite
programming relaxation of the problem.  In this thesis, we are able to
give a much simpler LP-based approximation algorithm using the vertex
multi-cut problem, which improves the approximation ratio to $O(\log
n)$ and also applies to a more general model.  Another direction of
work is based on SIS models for the worm spread, e.g., the
$n$-intertwined model \cite{orda:infocom09}. In this model, nodes are
in two states - susceptible or infected. Each infected node spreads
the infection to its neighbors with some probability. Another closely
related class of models is that of Interdependent Security games (IDS)
\cite{kearns:ids}, which is similar to our model for the special case
of $d = 1$.  One crucial technical difference between the two models,
which leads to two different games, is the assumption about the
initial infection: in IDS, it is assumed to originate independently at
different nodes, while in our $\GNS{1}$ model, we assume an initial
location is selected according to a given probability distribution.

Our formulation of generalized network security games is largely
motivated by mechanisms to protect communication networks.  Some of
our model and results, especially the lower bound results, however,
also apply equally well to the spread of diseases and the protection
of communities through vaccinations.  The pure Nash equilibria
correspond to stable points in the space of vaccination decisions made
by individuals, and our approximation algorithms yield public policies
for vaccination that well-approximate the social welfare.  There is
considerable work in epidemiology, both from a game-theoretic
perspective, as well as on the analysis of disease spreads through SIR
and SIS models~\cite{bauch04,bauch05,kessler08, barthelemy:jtb05,
  bauch:pnas03}.  The game-theoretic models adopted in these studies,
however, do not consider the impact of the underlying contact network.
Furthermore, there is little work on quantifying the effect of
locality (in disease spread or in information availability).
